package pers.qianyu.month_202012.date_20201203;

import org.junit.*;

import java.util.*;
import java.util.stream.*;

/**
 * 321. 拼接最大数
 * https://leetcode-cn.com/problems/create-maximum-number/
 * [优秀题解]：https://leetcode-cn.com/problems/create-maximum-number/solution/pin-jie-zui-da-shu-by-leetcode-solution/
 *
 * @author mizzle rain
 * @date 2020-12-02 17:41
 */
public class MaxNumber {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        // 创建比较器，用于排序
        TreeSet<List<Integer>> set = new TreeSet<>((list1, list2) -> {
            if (list1.size() == list2.size()) {
                for (int i = 0; i < list1.size(); i++) {
                    if (list1.get(i) > list2.get(i)) {
                        return -1;
                    }
                    if (list1.get(i) < list2.get(i)) {
                        return 1;
                    }
                }
            }
            return list2.size() - list1.size();
        });
        // 穷举所有情况
        for (int i = 0; i <= k; i++) {
            if (i <= nums1.length && k - i <= nums2.length) {
                List<Integer> list1 = solve(nums1, i);
                List<Integer> list2 = solve(nums2, k - i);
                set.add(merge(list1, list2));
            }
        }
        // 转换为数组
        List<Integer> list = set.pollFirst();
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    private List<Integer> solve(int[] nums, int k) {
        if (k == 0) {
            return new ArrayList<>();
        }
        if (k == nums.length) {
            return Arrays.stream(nums).boxed().collect(Collectors.toList());
        }
        int delCount = nums.length - k;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && delCount > 0 && nums[i] > stack.peek()) {
                stack.pop();
                delCount--;
            }
            stack.push(nums[i]);
        }
        if (delCount > 0) {
            return stack.stream().limit(k).collect(Collectors.toList());
        } else {
            return new ArrayList<>(stack);
        }
    }

    private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        if (list1 == null || list1.size() == 0) {
            return list2;
        }
        if (list2 == null || list2.size() == 0) {
            return list1;
        }
        List<Integer> res = new ArrayList<>();
        int len1 = list1.size();
        int len2 = list2.size();
        int i = 0, j = 0;
        while (i < len1 && j < len2) {
            // 不能只比较当前值，如果当前值相等还需要比较后续哪个大
            if (compare(list1, i, list2, j) > 0) {
                res.add(list1.get(i++));
            } else {
                res.add(list2.get(j++));
            }
            System.out.println(res);
        }
        while (i < len1) {
            res.add(list1.get(i++));
        }
        while (j < len2) {
            res.add(list2.get(j++));
        }
        return res;
    }

    private int compare(List<Integer> list1, int i, List<Integer> list2, int j) {
        if (j >= list2.size() && i >= list1.size()) {
            return 0;
        }
        if (i >= list1.size()) {
            return -1;
        }
        if (j >= list2.size()) {
            return 1;
        }
        if (list1.get(i) > list2.get(j)) {
            return 1;
        } else if (list1.get(i) < list2.get(j)) {
            return -1;
        } else {
            return compare(list1, i + 1, list2, j + 1);
        }
    }

    @Test
    public void test1() {
        int[] nums1 = {3, 4, 6, 5};
        int[] nums2 = {9, 1, 2, 5, 8, 3};
        int k = 5;
        int[] result = new MaxNumber().maxNumber(nums1, nums2, k);
        // 9, 8, 6, 5, 3
        System.out.println("result = " + Arrays.toString(result));
    }

    @Test
    public void test2() {
        int[] arr1 = {6, 7};
        int[] arr2 = {6, 0, 4};
        List<Integer> merge = merge(Arrays.stream(arr1).boxed().collect(Collectors.toList()),
                Arrays.stream(arr2).boxed().collect(Collectors.toList()));
        System.out.println(merge);
    }

    @Test
    public void test3() {
        int[] arr1 = {2, 5, 6, 4, 4, 0};
        int[] arr2 = {7, 3, 8, 0, 6, 5, 7, 6, 2};
        List<Integer> merge = merge(Arrays.stream(arr1).boxed().collect(Collectors.toList()),
                Arrays.stream(arr2).boxed().collect(Collectors.toList()));
        // [7,3,8,2,5,6,4,4,0,6,5,7,6,2,0]
        System.out.println(merge);
    }
}
